package 优先算法.双指针.三数之和;

import java.util.*;

/**
 * name 三数之和
 * <a href="https://leetcode.cn/problems/3sum/description/"
 */
public class TreeSum {
    public static void main(String[] args) {
        Solution so = new Solution();
//        int[] nums = {-1, 0, 1, 2, -1, -4};
        int[] nums = {0,0,0,0};
        System.out.println(so.threeSum(nums));
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //排顺序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        //找基准
        for (int tmp = 0; tmp < nums.length - 2; tmp++) {
            if (nums[tmp] > 0) break;
            //跳过重复的数
            if (tmp >= 1 && nums[tmp] == nums[tmp - 1]) {
                continue;
            }
            //双指针找基准和为相反数
            int abs_tmp = Math.abs(nums[tmp]);

            int left = tmp + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] > abs_tmp) {
                    right--;
                    while (nums[right + 1] == nums[right] && right < left) {
                        right--;
                    }

                } else if (nums[left] + nums[right] < abs_tmp) {
                    left++;
                    while (nums[left - 1] == nums[left] && left < right) {
                        left++;
                    }

                } else {
                    List<Integer> triplet = Arrays.asList(nums[tmp], nums[left], nums[right]);
                    result.add(triplet);
//                    List<Integer> sum = new ArrayList<Integer>();
//                    sum.add(nums[tmp]);
//                    sum.add(nums[left]);
//                    sum.add(nums[right]);

                    left++;
                    //去重
                    while (nums[left - 1] == nums[left] && left < right) {
                        left++;
                    }

                    right--;
                    //去重
                    while (nums[right + 1] == nums[right] && left < right) {
                        right--;
                    }

//                    result.add(sum);
                }

            }
        }
//    //set去重
//    Set<List<Integer>> resultSet = new HashSet<List<Integer>>(result);
//    return new ArrayList<>(resultSet);
        return result;
    }
}